home *** CD-ROM | disk | FTP | other *** search
/ FishMarket 1.0 / FishMarket v1.0.iso / fishies / 401-425 / disk_407 / flex / src.lzh / src / tblcmp.c < prev    next >
C/C++ Source or Header  |  1990-06-27  |  25KB  |  926 lines
  1. /* tblcmp - table compression routines */
  2.  
  3. /*-
  4.  * Copyright (c) 1990 The Regents of the University of California.
  5.  * All rights reserved.
  6.  *
  7.  * This code is derived from software contributed to Berkeley by
  8.  * Vern Paxson.
  9.  * 
  10.  * The United States Government has rights in this work pursuant
  11.  * to contract no. DE-AC03-76SF00098 between the United States
  12.  * Department of Energy and the University of California.
  13.  *
  14.  * Redistribution and use in source and binary forms are permitted provided
  15.  * that: (1) source distributions retain this entire copyright notice and
  16.  * comment, and (2) distributions including binaries display the following
  17.  * acknowledgement:  ``This product includes software developed by the
  18.  * University of California, Berkeley and its contributors'' in the
  19.  * documentation or other materials provided with the distribution and in
  20.  * all advertising materials mentioning features or use of this software.
  21.  * Neither the name of the University nor the names of its contributors may
  22.  * be used to endorse or promote products derived from this software without
  23.  * specific prior written permission.
  24.  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
  25.  * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
  26.  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  27.  */
  28.  
  29. #ifndef lint
  30. static char rcsid[] =
  31.     "@(#) $Header: /usr/fsys/odin/a/vern/flex/RCS/tblcmp.c,v 2.5 90/06/27 23:48:38 vern Exp $ (LBL)";
  32. #endif
  33.  
  34. #include "flexdef.h"
  35.  
  36.  
  37. /* declarations for functions that have forward references */
  38.  
  39. void mkentry PROTO((register int*, int, int, int, int));
  40. void mkprot PROTO((int[], int, int));
  41. void mktemplate PROTO((int[], int, int));
  42. void mv2front PROTO((int));
  43. int tbldiff PROTO((int[], int, int[]));
  44.  
  45.  
  46. /* bldtbl - build table entries for dfa state
  47.  *
  48.  * synopsis
  49.  *   int state[numecs], statenum, totaltrans, comstate, comfreq;
  50.  *   bldtbl( state, statenum, totaltrans, comstate, comfreq );
  51.  *
  52.  * State is the statenum'th dfa state.  It is indexed by equivalence class and
  53.  * gives the number of the state to enter for a given equivalence class.
  54.  * totaltrans is the total number of transitions out of the state.  Comstate
  55.  * is that state which is the destination of the most transitions out of State.
  56.  * Comfreq is how many transitions there are out of State to Comstate.
  57.  *
  58.  * A note on terminology:
  59.  *    "protos" are transition tables which have a high probability of
  60.  * either being redundant (a state processed later will have an identical
  61.  * transition table) or nearly redundant (a state processed later will have
  62.  * many of the same out-transitions).  A "most recently used" queue of
  63.  * protos is kept around with the hope that most states will find a proto
  64.  * which is similar enough to be usable, and therefore compacting the
  65.  * output tables.
  66.  *    "templates" are a special type of proto.  If a transition table is
  67.  * homogeneous or nearly homogeneous (all transitions go to the same
  68.  * destination) then the odds are good that future states will also go
  69.  * to the same destination state on basically the same character set.
  70.  * These homogeneous states are so common when dealing with large rule
  71.  * sets that they merit special attention.  If the transition table were
  72.  * simply made into a proto, then (typically) each subsequent, similar
  73.  * state will differ from the proto for two out-transitions.  One of these
  74.  * out-transitions will be that character on which the proto does not go
  75.  * to the common destination, and one will be that character on which the
  76.  * state does not go to the common destination.  Templates, on the other
  77.  * hand, go to the common state on EVERY transition character, and therefore
  78.  * cost only one difference.
  79.  */
  80.  
  81. void bldtbl( state, statenum, totaltrans, comstate, comfreq )
  82. int state[], statenum, totaltrans, comstate, comfreq;
  83.  
  84.     {
  85.     int extptr, extrct[2][CSIZE + 1];
  86.     int mindiff, minprot, i, d;
  87.     int checkcom;
  88.  
  89.     /* If extptr is 0 then the first array of extrct holds the result of the
  90.      * "best difference" to date, which is those transitions which occur in
  91.      * "state" but not in the proto which, to date, has the fewest differences
  92.      * between itself and "state".  If extptr is 1 then the second array of
  93.      * extrct hold the best difference.  The two arrays are toggled
  94.      * between so that the best difference to date can be kept around and
  95.      * also a difference just created by checking against a candidate "best"
  96.      * proto.
  97.      */
  98.  
  99.     extptr = 0;
  100.  
  101.     /* if the state has too few out-transitions, don't bother trying to
  102.      * compact its tables
  103.      */
  104.  
  105.     if ( (totaltrans * 100) < (numecs * PROTO_SIZE_PERCENTAGE) )
  106.     mkentry( state, numecs, statenum, JAMSTATE, totaltrans );
  107.  
  108.     else
  109.     {
  110.     /* checkcom is true if we should only check "state" against
  111.      * protos which have the same "comstate" value
  112.      */
  113.  
  114.     checkcom = comfreq * 100 > totaltrans * CHECK_COM_PERCENTAGE;
  115.  
  116.     minprot = firstprot;
  117.     mindiff = totaltrans;
  118.  
  119.     if ( checkcom )
  120.         {
  121.         /* find first proto which has the same "comstate" */
  122.         for ( i = firstprot; i != NIL; i = protnext[i] )
  123.         if ( protcomst[i] == comstate )
  124.             {
  125.             minprot = i;
  126.             mindiff = tbldiff( state, minprot, extrct[extptr] );
  127.             break;
  128.             }
  129.         }
  130.  
  131.     else
  132.         {
  133.         /* since we've decided that the most common destination out
  134.          * of "state" does not occur with a high enough frequency,
  135.          * we set the "comstate" to zero, assuring that if this state
  136.          * is entered into the proto list, it will not be considered
  137.          * a template.
  138.          */
  139.         comstate = 0;
  140.  
  141.         if ( firstprot != NIL )
  142.         {
  143.         minprot = firstprot;
  144.         mindiff = tbldiff( state, minprot, extrct[extptr] );
  145.         }
  146.         }
  147.  
  148.     /* we now have the first interesting proto in "minprot".  If
  149.      * it matches within the tolerances set for the first proto,
  150.      * we don't want to bother scanning the rest of the proto list
  151.      * to see if we have any other reasonable matches.
  152.      */
  153.  
  154.     if ( mindiff * 100 > totaltrans * FIRST_MATCH_DIFF_PERCENTAGE )
  155.         { /* not a good enough match.  Scan the rest of the protos */
  156.         for ( i = minprot; i != NIL; i = protnext[i] )
  157.         {
  158.         d = tbldiff( state, i, extrct[1 - extptr] );
  159.         if ( d < mindiff )
  160.             {
  161.             extptr = 1 - extptr;
  162.             mindiff = d;
  163.             minprot = i;
  164.             }
  165.         }
  166.         }
  167.  
  168.     /* check if the proto we've decided on as our best bet is close
  169.      * enough to the state we want to match to be usable
  170.      */
  171.  
  172.     if ( mindiff * 100 > totaltrans * ACCEPTABLE_DIFF_PERCENTAGE )
  173.         {
  174.         /* no good.  If the state is homogeneous enough, we make a
  175.          * template out of it.  Otherwise, we make a proto.
  176.          */
  177.  
  178.         if ( comfreq * 100 >= totaltrans * TEMPLATE_SAME_PERCENTAGE )
  179.         mktemplate( state, statenum, comstate );
  180.  
  181.         else
  182.         {
  183.         mkprot( state, statenum, comstate );
  184.         mkentry( state, numecs, statenum, JAMSTATE, totaltrans );
  185.         }
  186.         }
  187.  
  188.     else
  189.         { /* use the proto */
  190.         mkentry( extrct[extptr], numecs, statenum,
  191.              prottbl[minprot], mindiff );
  192.  
  193.         /* if this state was sufficiently different from the proto
  194.          * we built it from, make it, too, a proto
  195.          */
  196.  
  197.         if ( mindiff * 100 >= totaltrans * NEW_PROTO_DIFF_PERCENTAGE )
  198.         mkprot( state, statenum, comstate );
  199.  
  200.         /* since mkprot added a new proto to the proto queue, it's possible
  201.          * that "minprot" is no longer on the proto queue (if it happened
  202.          * to have been the last entry, it would have been bumped off).
  203.          * If it's not there, then the new proto took its physical place
  204.          * (though logically the new proto is at the beginning of the
  205.          * queue), so in that case the following call will do nothing.
  206.          */
  207.  
  208.         mv2front( minprot );
  209.         }
  210.     }
  211.     }
  212.  
  213.  
  214. /* cmptmps - compress template table entries
  215.  *
  216.  * synopsis
  217.  *    cmptmps();
  218.  *
  219.  *  template tables are compressed by using the 'template equivalence
  220.  *  classes', which are collections of transition character equivalence
  221.  *  classes which always appear together in templates - really meta-equivalence
  222.  *  classes.  until this point, the tables for templates have been stored
  223.  *  up at the top end of the nxt array; they will now be compressed and have
  224.  *  table entries made for them.
  225.  */
  226.  
  227. void cmptmps()
  228.  
  229.     {
  230.     int tmpstorage[CSIZE + 1];
  231.     register int *tmp = tmpstorage, i, j;
  232.     int totaltrans, trans;
  233.  
  234.     peakpairs = numtemps * numecs + tblend;
  235.  
  236.     if ( usemecs )
  237.     {
  238.     /* create equivalence classes base on data gathered on template
  239.      * transitions
  240.      */
  241.  
  242.     nummecs = cre8ecs( tecfwd, tecbck, numecs );
  243.     }
  244.     
  245.     else
  246.     nummecs = numecs;
  247.  
  248.     if ( lastdfa + numtemps + 1 >= current_max_dfas )
  249.     increase_max_dfas();
  250.  
  251.     /* loop through each template */
  252.  
  253.     for ( i = 1; i <= numtemps; ++i )
  254.     {
  255.     totaltrans = 0;    /* number of non-jam transitions out of this template */
  256.  
  257.     for ( j = 1; j <= numecs; ++j )
  258.         {
  259.         trans = tnxt[numecs * i + j];
  260.  
  261.         if ( usemecs )
  262.         {
  263.         /* the absolute value of tecbck is the meta-equivalence class
  264.          * of a given equivalence class, as set up by cre8ecs
  265.          */
  266.         if ( tecbck[j] > 0 )
  267.             {
  268.             tmp[tecbck[j]] = trans;
  269.  
  270.             if ( trans > 0 )
  271.             ++totaltrans;
  272.             }
  273.         }
  274.  
  275.         else
  276.         {
  277.         tmp[j] = trans;
  278.  
  279.         if ( trans > 0 )
  280.             ++totaltrans;
  281.         }
  282.         }
  283.  
  284.     /* it is assumed (in a rather subtle way) in the skeleton that
  285.      * if we're using meta-equivalence classes, the def[] entry for
  286.      * all templates is the jam template, i.e., templates never default
  287.      * to other non-jam table entries (e.g., another template)
  288.      */
  289.  
  290.     /* leave room for the jam-state after the last real state */
  291.     mkentry( tmp, nummecs, lastdfa + i + 1, JAMSTATE, totaltrans );
  292.     }
  293.     }
  294.  
  295.  
  296.  
  297. /* expand_nxt_chk - expand the next check arrays */
  298.  
  299. void expand_nxt_chk()
  300.  
  301.     {
  302.     register int old_max = current_max_xpairs;
  303.  
  304.     current_max_xpairs += MAX_XPAIRS_INCREMENT;
  305.  
  306.     ++num_reallocs;
  307.  
  308.     nxt = reallocate_integer_array( nxt, current_max_xpairs );
  309.     chk = reallocate_integer_array( chk, current_max_xpairs );
  310.  
  311.     bzero( (char *) (chk + old_max),
  312.        MAX_XPAIRS_INCREMENT * sizeof( int ) / sizeof( char ) );
  313.     }
  314.  
  315.  
  316. /* find_table_space - finds a space in the table for a state to be placed
  317.  *
  318.  * synopsis
  319.  *     int *state, numtrans, block_start;
  320.  *     int find_table_space();
  321.  *
  322.  *     block_start = find_table_space( state, numtrans );
  323.  *
  324.  * State is the state to be added to the full speed transition table.
  325.  * Numtrans is the number of out-transitions for the state.
  326.  *
  327.  * find_table_space() returns the position of the start of the first block (in
  328.  * chk) able to accommodate the state
  329.  *
  330.  * In determining if a state will or will not fit, find_table_space() must take
  331.  * into account the fact that an end-of-buffer state will be added at [0],
  332.  * and an action number will be added in [-1].
  333.  */
  334.  
  335. int find_table_space( state, numtrans )
  336. int *state, numtrans;
  337.     
  338.     {
  339.     /* firstfree is the position of the first possible occurrence of two
  340.      * consecutive unused records in the chk and nxt arrays
  341.      */
  342.     register int i;
  343.     register int *state_ptr, *chk_ptr;
  344.     register int *ptr_to_last_entry_in_state;
  345.  
  346.     /* if there are too many out-transitions, put the state at the end of
  347.      * nxt and chk
  348.      */
  349.     if ( numtrans > MAX_XTIONS_FULL_INTERIOR_FIT )
  350.     {
  351.     /* if table is empty, return the first available spot in chk/nxt,
  352.      * which should be 1
  353.      */
  354.     if ( tblend < 2 )
  355.         return ( 1 );
  356.  
  357.     i = tblend - numecs;    /* start searching for table space near the
  358.                  * end of chk/nxt arrays
  359.                  */
  360.     }
  361.  
  362.     else
  363.     i = firstfree;        /* start searching for table space from the
  364.                  * beginning (skipping only the elements
  365.                  * which will definitely not hold the new
  366.                  * state)
  367.                  */
  368.  
  369.     while ( 1 )        /* loops until a space is found */
  370.     {
  371.     if ( i + numecs > current_max_xpairs )
  372.         expand_nxt_chk();
  373.  
  374.     /* loops until space for end-of-buffer and action number are found */
  375.     while ( 1 )
  376.         {
  377.         if ( chk[i - 1] == 0 )    /* check for action number space */
  378.         {
  379.         if ( chk[i] == 0 )    /* check for end-of-buffer space */
  380.             break;
  381.  
  382.         else
  383.             i += 2;    /* since i != 0, there is no use checking to
  384.                  * see if (++i) - 1 == 0, because that's the
  385.                  * same as i == 0, so we skip a space
  386.                  */
  387.         }
  388.  
  389.         else
  390.         ++i;
  391.  
  392.         if ( i + numecs > current_max_xpairs )
  393.         expand_nxt_chk();
  394.         }
  395.  
  396.     /* if we started search from the beginning, store the new firstfree for
  397.      * the next call of find_table_space()
  398.      */
  399.     if ( numtrans <= MAX_XTIONS_FULL_INTERIOR_FIT )
  400.         firstfree = i + 1;
  401.  
  402.     /* check to see if all elements in chk (and therefore nxt) that are
  403.      * needed for the new state have not yet been taken
  404.      */
  405.  
  406.     state_ptr = &state[1];
  407.     ptr_to_last_entry_in_state = &chk[i + numecs + 1];
  408.  
  409.     for ( chk_ptr = &chk[i + 1]; chk_ptr != ptr_to_last_entry_in_state;
  410.           ++chk_ptr )
  411.         if ( *(state_ptr++) != 0 && *chk_ptr != 0 )
  412.         break;
  413.  
  414.     if ( chk_ptr == ptr_to_last_entry_in_state )
  415.         return ( i );
  416.  
  417.     else
  418.         ++i;
  419.     }
  420.     }
  421.  
  422.  
  423. /* inittbl - initialize transition tables
  424.  *
  425.  * synopsis
  426.  *   inittbl();
  427.  *
  428.  * Initializes "firstfree" to be one beyond the end of the table.  Initializes
  429.  * all "chk" entries to be zero.  Note that templates are built in their
  430.  * own tbase/tdef tables.  They are shifted down to be contiguous
  431.  * with the non-template entries during table generation.
  432.  */
  433. void inittbl()
  434.  
  435.     {
  436.     register int i;
  437.  
  438.     bzero( (char *) chk, current_max_xpairs * sizeof( int ) / sizeof( char ) );
  439.  
  440.     tblend = 0;
  441.     firstfree = tblend + 1;
  442.     numtemps = 0;
  443.  
  444.     if ( usemecs )
  445.     {
  446.     /* set up doubly-linked meta-equivalence classes
  447.      * these are sets of equivalence classes which all have identical
  448.      * transitions out of TEMPLATES
  449.      */
  450.  
  451.     tecbck[1] = NIL;
  452.  
  453.     for ( i = 2; i <= numecs; ++i )
  454.         {
  455.         tecbck[i] = i - 1;
  456.         tecfwd[i - 1] = i;
  457.         }
  458.  
  459.     tecfwd[numecs] = NIL;
  460.     }
  461.     }
  462.  
  463.  
  464. /* mkdeftbl - make the default, "jam" table entries
  465.  *
  466.  * synopsis
  467.  *   mkdeftbl();
  468.  */
  469.  
  470. void mkdeftbl()
  471.  
  472.     {
  473.     int i;
  474.  
  475.     jamstate = lastdfa + 1;
  476.  
  477.     ++tblend; /* room for transition on end-of-buffer character */
  478.  
  479.     if ( tblend + numecs > current_max_xpairs )
  480.     expand_nxt_chk();
  481.  
  482.     /* add in default end-of-buffer transition */
  483.     nxt[tblend] = end_of_buffer_state;
  484.     chk[tblend] = jamstate;
  485.  
  486.     for ( i = 1; i <= numecs; ++i )
  487.     {
  488.     nxt[tblend + i] = 0;
  489.     chk[tblend + i] = jamstate;
  490.     }
  491.  
  492.     jambase = tblend;
  493.  
  494.     base[jamstate] = jambase;
  495.     def[jamstate] = 0;
  496.  
  497.     tblend += numecs;
  498.     ++numtemps;
  499.     }
  500.  
  501.  
  502. /* mkentry - create base/def and nxt/chk entries for transition array
  503.  *
  504.  * synopsis
  505.  *   int state[numchars + 1], numchars, statenum, deflink, totaltrans;
  506.  *   mkentry( state, numchars, statenum, deflink, totaltrans );
  507.  *
  508.  * "state" is a transition array "numchars" characters in size, "statenum"
  509.  * is the offset to be used into the base/def tables, and "deflink" is the
  510.  * entry to put in the "def" table entry.  If "deflink" is equal to
  511.  * "JAMSTATE", then no attempt will be made to fit zero entries of "state"
  512.  * (i.e., jam entries) into the table.  It is assumed that by linking to
  513.  * "JAMSTATE" they will be taken care of.  In any case, entries in "state"
  514.  * marking transitions to "SAME_TRANS" are treated as though they will be
  515.  * taken care of by whereever "deflink" points.  "totaltrans" is the total
  516.  * number of transitions out of the state.  If it is below a certain threshold,
  517.  * the tables are searched for an interior spot that will accommodate the
  518.  * state array.
  519.  */
  520.  
  521. void mkentry( state, numchars, statenum, deflink, totaltrans )
  522. register int *state;
  523. int numchars, statenum, deflink, totaltrans;
  524.  
  525.     {
  526.     register int minec, maxec, i, baseaddr;
  527.     int tblbase, tbllast;
  528.  
  529.     if ( totaltrans == 0 )
  530.     { /* there are no out-transitions */
  531.     if ( deflink == JAMSTATE )
  532.         base[statenum] = JAMSTATE;
  533.     else
  534.         base[statenum] = 0;
  535.  
  536.     def[statenum] = deflink;
  537.     return;
  538.     }
  539.  
  540.     for ( minec = 1; minec <= numchars; ++minec )
  541.     {
  542.     if ( state[minec] != SAME_TRANS )
  543.         if ( state[minec] != 0 || deflink != JAMSTATE )
  544.         break;
  545.     }
  546.  
  547.     if ( totaltrans == 1 )
  548.     {
  549.     /* there's only one out-transition.  Save it for later to fill
  550.      * in holes in the tables.
  551.      */
  552.     stack1( statenum, minec, state[minec], deflink );
  553.     return;
  554.     }
  555.  
  556.     for ( maxec = numchars; maxec > 0; --maxec )
  557.     {
  558.     if ( state[maxec] != SAME_TRANS )
  559.         if ( state[maxec] != 0 || deflink != JAMSTATE )
  560.         break;
  561.     }
  562.  
  563.     /* Whether we try to fit the state table in the middle of the table
  564.      * entries we have already generated, or if we just take the state
  565.      * table at the end of the nxt/chk tables, we must make sure that we
  566.      * have a valid base address (i.e., non-negative).  Note that not only are
  567.      * negative base addresses dangerous at run-time (because indexing the
  568.      * next array with one and a low-valued character might generate an
  569.      * array-out-of-bounds error message), but at compile-time negative
  570.      * base addresses denote TEMPLATES.
  571.      */
  572.  
  573.     /* find the first transition of state that we need to worry about. */
  574.     if ( totaltrans * 100 <= numchars * INTERIOR_FIT_PERCENTAGE )
  575.     { /* attempt to squeeze it into the middle of the tabls */
  576.     baseaddr = firstfree;
  577.  
  578.     while ( baseaddr < minec )
  579.         {
  580.         /* using baseaddr would result in a negative base address below
  581.          * find the next free slot
  582.          */
  583.         for ( ++baseaddr; chk[baseaddr] != 0; ++baseaddr )
  584.         ;
  585.         }
  586.  
  587.     if ( baseaddr + maxec - minec >= current_max_xpairs )
  588.         expand_nxt_chk();
  589.  
  590.     for ( i = minec; i <= maxec; ++i )
  591.         if ( state[i] != SAME_TRANS )
  592.         if ( state[i] != 0 || deflink != JAMSTATE )
  593.             if ( chk[baseaddr + i - minec] != 0 )
  594.             { /* baseaddr unsuitable - find another */
  595.             for ( ++baseaddr;
  596.                   baseaddr < current_max_xpairs &&
  597.                   chk[baseaddr] != 0;
  598.                   ++baseaddr )
  599.                 ;
  600.  
  601.             if ( baseaddr + maxec - minec >= current_max_xpairs )
  602.                 expand_nxt_chk();
  603.  
  604.             /* reset the loop counter so we'll start all
  605.              * over again next time it's incremented
  606.              */
  607.  
  608.             i = minec - 1;
  609.             }
  610.     }
  611.  
  612.     else
  613.     {
  614.     /* ensure that the base address we eventually generate is
  615.      * non-negative
  616.      */
  617.     baseaddr = max( tblend + 1, minec );
  618.     }
  619.  
  620.     tblbase = baseaddr - minec;
  621.     tbllast = tblbase + maxec;
  622.  
  623.     if ( tbllast >= current_max_xpairs )
  624.     expand_nxt_chk();
  625.  
  626.     base[statenum] = tblbase;
  627.     def[statenum] = deflink;
  628.  
  629.     for ( i = minec; i <= maxec; ++i )
  630.     if ( state[i] != SAME_TRANS )
  631.         if ( state[i] != 0 || deflink != JAMSTATE )
  632.         {
  633.         nxt[tblbase + i] = state[i];
  634.         chk[tblbase + i] = statenum;
  635.         }
  636.  
  637.     if ( baseaddr == firstfree )
  638.     /* find next free slot in tables */
  639.     for ( ++firstfree; chk[firstfree] != 0; ++firstfree )
  640.         ;
  641.  
  642.     tblend = max( tblend, tbllast );
  643.     }
  644.  
  645.  
  646. /* mk1tbl - create table entries for a state (or state fragment) which
  647.  *            has only one out-transition
  648.  *
  649.  * synopsis
  650.  *   int state, sym, onenxt, onedef;
  651.  *   mk1tbl( state, sym, onenxt, onedef );
  652.  */
  653.  
  654. void mk1tbl( state, sym, onenxt, onedef )
  655. int state, sym, onenxt, onedef;
  656.  
  657.     {
  658.     if ( firstfree < sym )
  659.     firstfree = sym;
  660.  
  661.     while ( chk[firstfree] != 0 )
  662.     if ( ++firstfree >= current_max_xpairs )
  663.         expand_nxt_chk();
  664.  
  665.     base[state] = firstfree - sym;
  666.     def[state] = onedef;
  667.     chk[firstfree] = state;
  668.     nxt[firstfree] = onenxt;
  669.  
  670.     if ( firstfree > tblend )
  671.     {
  672.     tblend = firstfree++;
  673.  
  674.     if ( firstfree >= current_max_xpairs )
  675.         expand_nxt_chk();
  676.     }
  677.     }
  678.  
  679.  
  680. /* mkprot - create new proto entry
  681.  *
  682.  * synopsis
  683.  *   int state[], statenum, comstate;
  684.  *   mkprot( state, statenum, comstate );
  685.  */
  686.  
  687. void mkprot( state, statenum, comstate )
  688. int state[], statenum, comstate;
  689.  
  690.     {
  691.     int i, slot, tblbase;
  692.  
  693.     if ( ++numprots >= MSP || numecs * numprots >= PROT_SAVE_SIZE )
  694.     {
  695.     /* gotta make room for the new proto by dropping last entry in
  696.      * the queue
  697.      */
  698.     slot = lastprot;
  699.     lastprot = protprev[lastprot];
  700.     protnext[lastprot] = NIL;
  701.     }
  702.  
  703.     else
  704.     slot = numprots;
  705.  
  706.     protnext[slot] = firstprot;
  707.  
  708.     if ( firstprot != NIL )
  709.     protprev[firstprot] = slot;
  710.  
  711.     firstprot = slot;
  712.     prottbl[slot] = statenum;
  713.     protcomst[slot] = comstate;
  714.  
  715.     /* copy state into save area so it can be compared with rapidly */
  716.     tblbase = numecs * (slot - 1);
  717.  
  718.     for ( i = 1; i <= numecs; ++i )
  719.     protsave[tblbase + i] = state[i];
  720.     }
  721.  
  722.  
  723. /* mktemplate - create a template entry based on a state, and connect the state
  724.  *              to it
  725.  *
  726.  * synopsis
  727.  *   int state[], statenum, comstate, totaltrans;
  728.  *   mktemplate( state, statenum, comstate, totaltrans );
  729.  */
  730.  
  731. void mktemplate( state, statenum, comstate )
  732. int state[], statenum, comstate;
  733.  
  734.     {
  735.     int i, numdiff, tmpbase, tmp[CSIZE + 1];
  736.     Char transset[CSIZE + 1];
  737.     int tsptr;
  738.  
  739.     ++numtemps;
  740.  
  741.     tsptr = 0;
  742.  
  743.     /* calculate where we will temporarily store the transition table
  744.      * of the template in the tnxt[] array.  The final transition table
  745.      * gets created by cmptmps()
  746.      */
  747.  
  748.     tmpbase = numtemps * numecs;
  749.  
  750.     if ( tmpbase + numecs >= current_max_template_xpairs )
  751.     {
  752.     current_max_template_xpairs += MAX_TEMPLATE_XPAIRS_INCREMENT;
  753.  
  754.     ++num_reallocs;
  755.  
  756.     tnxt = reallocate_integer_array( tnxt, current_max_template_xpairs );
  757.     }
  758.  
  759.     for ( i = 1; i <= numecs; ++i )
  760.     if ( state[i] == 0 )
  761.         tnxt[tmpbase + i] = 0;
  762.     else
  763.         {
  764.         transset[tsptr++] = i;
  765.         tnxt[tmpbase + i] = comstate;
  766.         }
  767.  
  768.     if ( usemecs )
  769.     mkeccl( transset, tsptr, tecfwd, tecbck, numecs, 0 );
  770.  
  771.     mkprot( tnxt + tmpbase, -numtemps, comstate );
  772.  
  773.     /* we rely on the fact that mkprot adds things to the beginning
  774.      * of the proto queue
  775.      */
  776.  
  777.     numdiff = tbldiff( state, firstprot, tmp );
  778.     mkentry( tmp, numecs, statenum, -numtemps, numdiff );
  779.     }
  780.  
  781.  
  782. /* mv2front - move proto queue element to front of queue
  783.  *
  784.  * synopsis
  785.  *   int qelm;
  786.  *   mv2front( qelm );
  787.  */
  788.  
  789. void mv2front( qelm )
  790. int qelm;
  791.  
  792.     {
  793.     if ( firstprot != qelm )
  794.     {
  795.     if ( qelm == lastprot )
  796.         lastprot = protprev[lastprot];
  797.  
  798.     protnext[protprev[qelm]] = protnext[qelm];
  799.  
  800.     if ( protnext[qelm] != NIL )
  801.         protprev[protnext[qelm]] = protprev[qelm];
  802.  
  803.     protprev[qelm] = NIL;
  804.     protnext[qelm] = firstprot;
  805.     protprev[firstprot] = qelm;
  806.     firstprot = qelm;
  807.     }
  808.     }
  809.  
  810.  
  811. /* place_state - place a state into full speed transition table
  812.  *
  813.  * synopsis
  814.  *     int *state, statenum, transnum;
  815.  *     place_state( state, statenum, transnum );
  816.  *
  817.  * State is the statenum'th state.  It is indexed by equivalence class and
  818.  * gives the number of the state to enter for a given equivalence class.
  819.  * Transnum is the number of out-transitions for the state.
  820.  */
  821.  
  822. void place_state( state, statenum, transnum )
  823. int *state, statenum, transnum;
  824.  
  825.     {
  826.     register int i;
  827.     register int *state_ptr;
  828.     int position = find_table_space( state, transnum );
  829.  
  830.     /* base is the table of start positions */
  831.     base[statenum] = position;
  832.  
  833.     /* put in action number marker; this non-zero number makes sure that
  834.      * find_table_space() knows that this position in chk/nxt is taken
  835.      * and should not be used for another accepting number in another state
  836.      */
  837.     chk[position - 1] = 1;
  838.  
  839.     /* put in end-of-buffer marker; this is for the same purposes as above */
  840.     chk[position] = 1;
  841.  
  842.     /* place the state into chk and nxt */
  843.     state_ptr = &state[1];
  844.  
  845.     for ( i = 1; i <= numecs; ++i, ++state_ptr )
  846.     if ( *state_ptr != 0 )
  847.         {
  848.         chk[position + i] = i;
  849.         nxt[position + i] = *state_ptr;
  850.         }
  851.  
  852.     if ( position + numecs > tblend )
  853.     tblend = position + numecs;
  854.     }
  855.  
  856.  
  857. /* stack1 - save states with only one out-transition to be processed later
  858.  *
  859.  * synopsis
  860.  *   int statenum, sym, nextstate, deflink;
  861.  *   stack1( statenum, sym, nextstate, deflink );
  862.  *
  863.  * if there's room for another state one the "one-transition" stack, the
  864.  * state is pushed onto it, to be processed later by mk1tbl.  If there's
  865.  * no room, we process the sucker right now.
  866.  */
  867.  
  868. void stack1( statenum, sym, nextstate, deflink )
  869. int statenum, sym, nextstate, deflink;
  870.  
  871.     {
  872.     if ( onesp >= ONE_STACK_SIZE - 1 )
  873.     mk1tbl( statenum, sym, nextstate, deflink );
  874.  
  875.     else
  876.     {
  877.     ++onesp;
  878.     onestate[onesp] = statenum;
  879.     onesym[onesp] = sym;
  880.     onenext[onesp] = nextstate;
  881.     onedef[onesp] = deflink;
  882.     }
  883.     }
  884.  
  885.  
  886. /* tbldiff - compute differences between two state tables
  887.  *
  888.  * synopsis
  889.  *   int state[], pr, ext[];
  890.  *   int tbldiff, numdifferences;
  891.  *   numdifferences = tbldiff( state, pr, ext )
  892.  *
  893.  * "state" is the state array which is to be extracted from the pr'th
  894.  * proto.  "pr" is both the number of the proto we are extracting from
  895.  * and an index into the save area where we can find the proto's complete
  896.  * state table.  Each entry in "state" which differs from the corresponding
  897.  * entry of "pr" will appear in "ext".
  898.  * Entries which are the same in both "state" and "pr" will be marked
  899.  * as transitions to "SAME_TRANS" in "ext".  The total number of differences
  900.  * between "state" and "pr" is returned as function value.  Note that this
  901.  * number is "numecs" minus the number of "SAME_TRANS" entries in "ext".
  902.  */
  903.  
  904. int tbldiff( state, pr, ext )
  905. int state[], pr, ext[];
  906.  
  907.     {
  908.     register int i, *sp = state, *ep = ext, *protp;
  909.     register int numdiff = 0;
  910.  
  911.     protp = &protsave[numecs * (pr - 1)];
  912.  
  913.     for ( i = numecs; i > 0; --i )
  914.     {
  915.     if ( *++protp == *++sp )
  916.         *++ep = SAME_TRANS;
  917.     else
  918.         {
  919.         *++ep = *sp;
  920.         ++numdiff;
  921.         }
  922.     }
  923.  
  924.     return ( numdiff );
  925.     }
  926.